package com.cuz.daileetcode.bat100;


/***
 * 数组arr 表述数字序列
 * 问递增子序列最长的长度
 */
public class 最长递增子序列 {

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 4, 5, 6, 1, 6, 8, 1,1,1,1,10,2,11};
        System.out.println(solution1(arr));
        System.out.println(solution2(arr));
    }

    public static int solution1(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr == null ? 0 : arr.length;
        }
        int len = arr.length;
        //dp【i】 以i结尾的数组递增最长有多长
        int[] dp = new int[len];
        dp[0] = 1;
        int ans = 1;
        for (int i = 1; i < len; i++) {
            dp[i] = 1;
            //向前找 更新dp[i] （如果arr[i] > arr[j]表示i位置数 可以接在这个数后面）
            for (int j = i - 1; j >= 0; j--) {
                //6,7,8,1,2,3,4
                //i=6  j=3 dp[i]=4
                //这个时候j-- j=2 表示前面只有j+1个数 也就3个数没有办法让dp【i】更大了
                if (dp[i] > j + 1) {
                    break;
                }
                //当前数 大于前面这个数
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }


    public static int solution2(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr == null ? 0 : arr.length;
        }
        int len = arr.length;
        //dp【i】 以i结尾的数组递增最长有多长
        int[] dp = new int[len];
        int ans = 1;
        //endNumArr[i] 表示长度为i+1 的子序列末尾的数为endNumArr[i]
        //意味这 【0-ans-1】 位置上的数才是有意义的
        int[] endNumArr = new int[len];
        endNumArr[0] = arr[0];
        for (int i = 1; i < len; i++) {
            int lessThanIndex = findLastLessThan(endNumArr, arr[i], 0, ans);
            if (lessThanIndex == -1) {
                dp[i] = 1;
                endNumArr[0] = Math.min(endNumArr[0], arr[i]);
            } else {
                dp[i] = lessThanIndex + 1;
                if (dp[i] < ans) {
                    endNumArr[lessThanIndex] = Math.min(endNumArr[lessThanIndex], arr[i]);
                } else {
                    endNumArr[lessThanIndex] = arr[i];
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    private static int findLastLessThan(int[] arr, int target, int start, int end) {
        int left = start - 1;
        int right = end + 1;
        while (left + 1 != right) {
            int mid = ((right - left) >> 1) + left;
            if (arr[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (left < 0 || left >= arr.length) {
            return -1;
        }
        return arr[left] < target ? left : -1;
    }
}
